# ifndef __PtAlgo_H_
# define __PtAlgo_H_

//
// PtAlgo.h
//
// Definitions of basic geometry types: point, rectangle etc.
// NOTE: 4-byte float is used everywhere to save memory.
//

# include <vector>


//
// Point.
//
struct point_t {
	// Longitude and latitude, in degrees.
	float x, y;

	point_t () {}
	point_t (float _x, float _y) : x (_x), y (_y) {}

	bool operator == (const point_t & _other) const {return x == _other.x && y == _other.y;}
};

inline
point_t operator+ (const point_t & _a, const point_t & _b) {
	return point_t (_a.x + _b.x, _a.y + _b.y);
}

inline
point_t operator* (const point_t & _a, float _k) {
	return point_t (_a.x*_k, _a.y*_k);
}

inline
point_t operator- (const point_t & _a, const point_t & _b) {
	return point_t (_a.x - _b.x, _a.y - _b.y);
}

typedef std::vector<point_t> points_t;

bool IsRightOriented (const points_t & _points);
float GetArea   (const points_t & _points);
float GetLength (float _x1, float _y1, float _x2, float _y2);
float GetLength (const point_t & _p1, const point_t & _p2);
float GetLength (const points_t & _points);
float GetLength (const points_t & _points, size_t _cBegin, size_t _cEnd);

bool PointContainsPt    (const point_t & _point, const point_t & _pt, float _e, float _fCosY);

// Return index of point or -1.
size_t PointsContainPt  (const points_t & _pts,  const point_t & _pt, float _e, float _fCosY);

bool PolylineContainsPt (const points_t & _pts,  const point_t & _pt, float _e, float _fCosY, bool _bLastChain = false, point_t * _pPoint = NULL, size_t * _pcPointIndex = NULL);
bool SegmentContainsPt (const point_t & _a, const point_t & _b, const point_t & _pt, float _e, float _fCosY);

// Returns 1 if point is entirely within polygon, 0 if it is on its border and -1 if it is outside polygon.
int PolygonContainsPt   (const points_t & _polygon, const point_t & _pt);

bool AreThereRepeatingPoints (const points_t & _points);
void RemoveRepeatingPoints (points_t & _points);

float Distance2 (const point_t & _p0, const point_t & _p1, float _fCos2Y);
float DistanceToSegment2 (
	const point_t & _ptA, const point_t & _ptB, const point_t & _pt, float _fCosY,
	point_t & _ptNearest
);
float GetNearestPointOfPolyline (
	const points_t & _points, size_t _cBegin, size_t _cEnd,
	const point_t & _pt,
	float _fCosY,
	point_t & _ptNearest, size_t & _cNearestSegment
);

float Distance2ToPolyline (const points_t & _points, const point_t & _p, float _fCosY);
float Distance2ToPolygon  (const points_t & _points, const point_t & _p, float _fCosY);


//
// Rectangle.
//
struct rect_t {
	// In degrees.
	float x0, y0, x1, y1;

	rect_t () : x0 (200), x1 (-200), y0 (200), y1 (-200) {}
	rect_t (float _x0, float _y0, float _x1, float _y1) : x0 (_x0), x1 (_x1), y0 (_y0), y1 (_y1) {}

	bool operator == (const rect_t & _other) {
		return x0 == _other.x0 && x1 == _other.x1 && y0 == _other.y0 && y1 == _other.y1;
	}

	void swap (rect_t & _other) {
		std::swap (x0, _other.x0);
		std::swap (y0, _other.y0);
		std::swap (x1, _other.x1);
		std::swap (y1, _other.y1);
	}

	float Width  () const {return x1 > x0 ? x1 - x0 : 0;}
	float Height () const {return y1 > y0 ? y1 - y0 : 0;}

	float MeanX () const {return (x0 + x1)/2;}
	float MeanY () const {return (y0 + y1)/2;}

	bool Empty () const {return x1 <= x0 || y1 <= y0;}
	bool Invalid () const {return x1 < x0 || y1 < y0;}

	bool Intersects (const rect_t & _rect) const {
		if (x1 < _rect.x0 || x0 > _rect.x1)
			return false;
		if (y1 < _rect.y0 || y0 > _rect.y1)
			return false;
		return true;
	}

	bool Contains (float _x, float _y) const {
		return _x >= x0 && _x <= x1 && _y >= y0 && _y <= y1;
	}

	bool Contains (const point_t & _point) const {
		return _point.x >= x0 && _point.x <= x1 && _point.y >= y0 && _point.y <= y1;
	}

	bool Contains (const rect_t & _rect) const {
		return x0 <= _rect.x0 && x1 >= _rect.x1 && y0 <= _rect.y0 && y1 >= _rect.y1;
	}

	void Shift (float _x, float _y) {
		x0 += _x;
		x1 += _x;
		y0 += _y;
		y1 += _y;
	}

	void Extend (const point_t & _point) {
		if (_point.x < x0) x0 = _point.x;
		if (_point.x > x1) x1 = _point.x;
		if (_point.y < y0) y0 = _point.y;
		if (_point.y > y1) y1 = _point.y;
	}

	void Extend (const rect_t & _rect) {
		if (_rect.x0 < x0) x0 = _rect.x0;
		if (_rect.x1 > x1) x1 = _rect.x1;
		if (_rect.y0 < y0) y0 = _rect.y0;
		if (_rect.y1 > y1) y1 = _rect.y1;
	}

	void Extend (const points_t & _points);

	static void Intersection (rect_t & _rectDest, const rect_t & _rectSrc1, const rect_t & _rectSrc2) {
		_rectDest.x0 = _rectSrc1.x0 > _rectSrc2.x0 ? _rectSrc1.x0 : _rectSrc2.x0;
		_rectDest.x1 = _rectSrc1.x1 < _rectSrc2.x1 ? _rectSrc1.x1 : _rectSrc2.x1;
		_rectDest.y0 = _rectSrc1.y0 > _rectSrc2.y0 ? _rectSrc1.y0 : _rectSrc2.y0;
		_rectDest.y1 = _rectSrc1.y1 < _rectSrc2.y1 ? _rectSrc1.y1 : _rectSrc2.y1;
	}
};

bool FrameContainsPt (const rect_t & _rect, const point_t & _pt, float _e, float _fCosY, size_t * _pcPointIndex = NULL);

bool RectIntersectsPolyline (const rect_t & _rect, const points_t & _points, bool _bClosed);

bool SegmentIntersectsPolyline (const point_t & _a, const point_t & _b, const points_t & _points, bool _bClosed);

struct pip_info_t {
	size_t cSegment1;
	size_t cSegment2;
};
bool PolylineIntersectsPolyline       (const points_t & _points1, const points_t & _points2, bool _bClosed, pip_info_t * _pInfo = NULL);
bool PolylineIntersectsSelf           (const points_t & _points,                             bool _bClosed, pip_info_t * _pInfo = NULL);
bool PolylineIntersectsPolylineInNode (const points_t & _points1, const points_t & _points2,                pip_info_t * _pInfo = NULL);
bool PolylineIntersectsSelfInNode     (const points_t & _points,                                            pip_info_t * _pInfo = NULL);

//
// Parameters of affine transformation.
//
struct aff_transform_t {
	// The matrix elements.
	float fAXx, fAXy, fAYx, fAYy;
	// The shift vector.
	float fBX, fBY;

	void ApplyTo (point_t & _p) const;
	void Multiply (const aff_transform_t & _at2, aff_transform_t & _result) const;
	void Reverse (aff_transform_t & _atReverse) const;
};

//
// Parameters of quadratic transformation.
//
struct q_transform_t : public aff_transform_t {
	float fDXxx, fDXxy, fDXyy, fDYxx, fDYxy, fDYyy;

	void ApplyTo (point_t & _p) const;
};

//
//
//

# include "NodesExtra.h"

struct epoint_t {
	point_t point;
	point_extra_t extra;
};
typedef std::vector<epoint_t> epoints_t;
typedef std::list<epoints_t> polyepoints_t;
typedef std::list<points_t>  polypoints_t;

void Points2EPoints (const points_t  & _points, const point_extras_t * _pPointExtras, epoints_t & _epoints);
void EPoints2Points (const epoints_t & _epoints, bool _bHasExtra, points_t & _points, point_extras_t & _PointExtras);

void RemoveRepeatingPoints (epoints_t & _epoints);

# endif // __PtAlgo_H_